import unittest.case
from typing import List, Dict, Tuple, Set


# 最大岛屿面积问题: https://leetcode-cn.com/problems/max-area-of-island/

# 解法1: 近似的DBSCAN解法, 其实是广度优先算法(DFS)
# 假定:
# - 输入x为二维数组
# - 如果x对应的为0, 则不与任何节点相连, 否则寻找上下左右相连的节点, 包括自身, 记为最小邻居节点数
# - 最小邻居节点数为1
# 性能优化
class Solution:
    @staticmethod
    def get_item(grid: List[list], _n_rows: int, _n_cols: int, _i: int, _j: int) -> int:
        if _i < 0 or _i >= _n_rows or _j < 0 or _j >= _n_cols:
            return 0
        else:
            return grid[_i][_j]

    @staticmethod
    def maxAreaOfIsland(grid: List[List[int]]) -> int:
        n_rows = len(grid)
        if n_rows <= 0:
            return 0
        n_cols = len(grid[0])
        if n_cols <= 0:
            return 0
        # 构建邻接表: (x坐标, y坐标): set((邻居节点x坐标, 邻居节点y坐标), ...)
        adjacency: Dict[Tuple[int, int], Set[Tuple[int, int]]] = {}
        for row in range(0, n_rows):
            for col in range(0, n_cols):
                _each = grid[row][col]
                if _each == 0:
                    continue
                for _i, _j in [(row, col), (row - 1, col), (row, col - 1), (row + 1, col), (row, col + 1)]:
                    if Solution.get_item(grid, n_rows, n_cols, _i, _j):
                        if (row, col) in adjacency:
                            adjacency[(row, col)].add((_i, _j))
                        else:
                            adjacency[(row, col)] = {(_i, _j)}

        # 近似DBSCAN求取聚类
        # ----
        # 已访问的点集, 由于二维数目非常大, 采用set而不是0-1数组: set((x,y), ...)
        visited = set()
        # 类簇结果信息, 同样原因采用dict: {(x, y): cluster_id}
        cluster: Dict[Tuple[int, int], int] = {}

        k = -1
        for (i, j), neighbors in adjacency.items():
            k += 1
            if (i, j) in visited:
                continue
            if len(neighbors) == 0:
                # option
                visited.add((i, j))
                cluster[(i, j)] = k
                # end option
                continue
            nb: set = neighbors.copy()
            while len(nb) > 0:
                n_i, n_j = nb.pop()
                if (n_i, n_j) in visited:
                    continue
                # option
                cluster[(n_i, n_j)] = k
                visited.add((n_i, n_j))
                # end option
                if (n_i, n_j) not in adjacency:
                    continue
                for each in adjacency[(n_i, n_j)]:
                    if each not in visited:
                        nb.add(each)

        mmm = {}
        for (i, j), v in cluster.items():
            if v in mmm:
                mmm[v].add((i, j))
            else:
                mmm[v] = {(i, j)}
        return max([len(each) for each in mmm.values()]) if len(mmm) > 0 else 0


class Max_area_of_island_suite(unittest.TestCase):
    def test_init(self):
        self.grid = [[0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
                     [0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
                     [0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0],
                     [0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
                     [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0]]
        self.grid2 = [[0, 0, 0, 0, 0, 0, 0, 0]]
        self.grid3 = [[0, 0, 0, 1, 0, 0, 0],
                      [0, 0, 0, 0, 1, 0, 0]]

    def test_max_area_by_dbscan(self):
        self.test_init()
        assert Solution.maxAreaOfIsland(self.grid) == 6
        assert Solution.maxAreaOfIsland(self.grid2) == 0
        assert Solution.maxAreaOfIsland(self.grid3) == 1


if __name__ == '__main__':
    unittest.main()
